package year2024.month4;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

import java.util.Arrays;

public class CoinChange {

    @Test
    void test1() {
        Assertions.assertEquals(3, coinChange(new int[]{1, 2, 5}, 11));
    }

    @Test
    void test2() {
        Assertions.assertEquals(-1, coinChange(new int[]{2}, 3));
    }

    @Test
    void test3() {
        Assertions.assertEquals(0, coinChange(new int[]{1}, 0));
    }

    @Test
    void test4() {
        Assertions.assertEquals(20, coinChange(new int[]{1, 2, 5}, 100));
    }

    @Test
    void test5() {
        Assertions.assertEquals(2, coinChange(new int[]{1,2147483647}, 2));
    }


    /**
     * 322 零钱兑换
     * 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
     * <p>
     * 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
     * <p>
     * 你可以认为每种硬币的数量是无限的。
     *
     * @param coins
     * @param amount
     * @return
     */
    public int coinChange(int[] coins, int amount) {

        if (amount == 0) {
            return 0;
        }

        int[] cache = new int[amount + 1];
        Arrays.fill(cache, -1);
        int result = coinChange(coins, amount, cache);

        if (result == 0) {
            return -1;
        }
        return result;
    }

    int coinChange(int[] coins, int amount, int[] cache) {

        int min = Integer.MAX_VALUE;

        int methods = cache[amount];
        if (methods != -1) {
            System.out.printf("amount = %d 缓存命中 %d\n", amount, methods);
            return methods;
        }

        for (int coin : coins) {
            int remain = amount - coin;

            if (remain > 0) {
                int coinCount = coinChange(coins, remain,cache);
                if (coinCount > 0) {
                    min = Math.min(min, coinCount);
                }

            } else if (remain == 0) {
                return cache[amount] = 1;
            }/* else {
                return cache[amount] = 0;
            }*/

        }

        if (min == Integer.MAX_VALUE) {
            return cache[amount] = 0;
        }

        return cache[amount] = (1 + min);
    }
}
